#include <bits/stdc++.h>
using namespace std;

/*
2929. 给小朋友们分糖果 II
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

 

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。
示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。
 

提示：

1 <= n <= 106
1 <= limit <= 106
*/

// 法一 三重暴力枚举
// 超时 但是答案应该没毛病
class Solution {
public:
    long long distributeCandies(int n, int limit) {
        // 三重枚举
        long long ans = 0;
        for (int i = 0; i <= limit; i++)
            for (int j = 0; j <= limit; j++)
                for (int k = 0; k <= limit; k++)
                    if (i + j + k == n)
                        ans++;
        return ans;
    }
};

// 法二 优化到二重循环
// 还是超时
class Solution {
public:
    long long distributeCandies(int n, int limit) {
        // 优化 双重循环
        long long ans = 0;
        for (int i = 0; i <= limit; i++)
            for (int j = 0; j <= limit; j++) {
                int k = n - i - j;
                if (k >= 0 && k <= limit)
                    ans++;
            }
        return ans;
    }
};

// 法三  互斥原理
class Solution {
public:
    long long distributeCandies(int n, int limit) {
        //    ans=C(n+2,2)−3⋅C(n−limit+1,2)+3⋅C(n−2⋅limit,2)−C(n−3⋅limit−1,2) 其中C(x,2)= x⋅(x−1)/2​  （当x≥2，否则为0）。
        return C2(n + 2) - 3 * C2(n - limit + 1) + 3 * C2(n - 2 * limit) - C2(n - 3 * limit - 1);
    }
    long long C2(int x) {
        return x >= 2 ? (long long)x * (x - 1) / 2 : 0;
    }
};

// 法四 ​​动态枚举与条件剪枝​​  动态规划与数学组合相结合
// 基础情况还是 n≤limit时，直接使用组合数学公式
class Solution {
public:
    long long distributeCandies(int n, int limit) {
        // 基本情况处理：当总糖果数不超过单个小朋友限制时
        // 使用组合数学公式计算无限制分配方案数（必然满足limit条件）
        if (n <= limit) 
            return 1LL * (n + 1) * (n + 2) / 2;  // C(n+2,2)组合数公式

        long long ans = 0;  // 存储最终方案数
        
        // 枚举第一个小朋友分到的糖果数i（0 ≤ i ≤ limit）
        for (int i = 0; i <= limit; i++) {
            int cur_surplus = n - i;  // 剩余待分配的糖果数
            
            // 剩余糖果超过两个小朋友的限制总和时跳过（无法合法分配）
            if (cur_surplus > 2 * limit) 
                continue;
            
            // 根据剩余糖果数计算第二个小朋友的合法分配方案数
            if (cur_surplus > limit) 
                // 当剩余糖果超过单个小朋友限制时：
                // 第二个小朋友的可分配范围为 [cur_surplus-limit, limit]
                // 方案数 = 2*limit - cur_surplus + 1
                ans += 1LL * (2 * limit - cur_surplus + 1);
            else 
                // 当剩余糖果在单个小朋友限制内时：
                // 第二个小朋友的可分配范围为 [0, cur_surplus]
                // 方案数 = cur_surplus + 1
                ans += cur_surplus + 1;
        }
        return ans;
    }
};






 
